<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  <title>蓝湖畔淅淅沥沥的雨</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta property="og:type" content="website">
<meta property="og:title" content="蓝湖畔淅淅沥沥的雨">
<meta property="og:url" content="http://example.com/page/8/index.html">
<meta property="og:site_name" content="蓝湖畔淅淅沥沥的雨">
<meta property="og:locale" content="zh_CN">
<meta property="article:author" content="StarsWhisper">
<meta name="twitter:card" content="summary">
  
    <link rel="alternate" href="/atom.xml" title="蓝湖畔淅淅沥沥的雨" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  
<link rel="stylesheet" href="/css/style.css">

  
<link rel="stylesheet" href="/plugin/bganimation/bg.css">

  

  <link href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css" rel="stylesheet" type="text/css">
<meta name="generator" content="Hexo 6.1.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <div class="outer">
        <div class="widget-wrap mobile-header">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

        <section id="main">
  
    <article id="post-筛法-素数" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E7%AD%9B%E6%B3%95-%E7%B4%A0%E6%95%B0/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E7%AD%9B%E6%B3%95-%E7%B4%A0%E6%95%B0/">筛法-素数.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/%E6%95%B0%E8%AE%BA/">数论</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<h3 id="埃拉托斯特尼筛法"><a class="markdownIt-Anchor" href="#埃拉托斯特尼筛法"></a> 埃拉托斯特尼筛法</h3>
<blockquote>
<p>埃拉托斯特尼筛法（The Sieve of Eratosthenes）：<br />
• 设u[]为筛子，初始时区间中的所有数在筛子u[]中。按递增顺序搜索u[]中的最小数，<br />
将其倍数从u[]中筛去，最终筛中留下的数即为素数。<br />
• int i, j, k; • for (i=2; i&lt;=n; i++) u[i]=true; //初始时所有数在筛中<br />
• for (i=2; i&lt;=n; i++) //顺序搜索筛中的最小数<br />
• if (u[i]) {<br />
• for (j=2; j _i &lt;=n; j++) //将i的倍数从筛中筛去<br />
• u[j_i]=false;<br />
• } • for (i=2; i&lt;=n; i++) if (u[i]) { //将筛中的所有素数放入su[]中 • su[++num]=i; • }<br />
• 上述算法的时间复杂度为O(n * log log n)。算法中合数是作为素数的倍数被筛去的。</p>
</blockquote>
<h3 id="欧拉筛法"><a class="markdownIt-Anchor" href="#欧拉筛法"></a> 欧拉筛法</h3>
<blockquote>
<p>如果每个合数仅被它最小的质因数筛去，则算法效率可以大幅提升。由此引 出一种优化的算法——欧拉筛法（Euler’s Sieve）：<br />
• int i, j, num=1;<br />
• memset(u, true, sizeof(u));<br />
• for (i=2; i&lt;=n; i++){ //顺序分析整数区间的每个数<br />
• if (u[i]) su[num++]=i; //将筛中最小数送入素数表<br />
• for (j=1; j&lt;num; j++) { //搜索素数表的每个数<br />
• if (i _su[j] &gt;n) break; //若i与当前素数的乘积超出范围，则分析下 一个整数i • u[i_su[j]]=false;<br />
//将i与当前素数的乘积从筛子中筛去<br />
• if (i%su[j]==0) break; //若当前素数为i的最小素因子，则分析下一 个整数i • } • } •<br />
欧拉筛法的时间复杂度可优化至O(n)。</p>
</blockquote>
<h3 id="题目1-牛牛的质因数"><a class="markdownIt-Anchor" href="#题目1-牛牛的质因数"></a> 题目1 牛牛的“质因数”</h3>
<p>大概题意是把每个数写成若干质因数连续排列的形式，如3=3,7=7，9=33，16=2222，1500=223555，然后给出一个n，然后在这种形式下求sum（2~n）。结果对1e+7取模<br />
此处TP：<a target="_blank" rel="noopener" href="https://ac.nowcoder.com/acm/contest/9982/I">https://ac.nowcoder.com/acm/contest/9982/I</a></p>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> LL;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">4e6</span>+<span class="number">5</span>;</span><br><span class="line"><span class="comment">//const int M = 4e6;</span></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> mod = <span class="number">1e9</span>+<span class="number">7</span>;</span><br><span class="line"><span class="type">bool</span> vis[N];</span><br><span class="line">LL dp[N];</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> M;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">getmul</span><span class="params">(<span class="type">int</span> x)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> re = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span>(x)</span><br><span class="line">    &#123;</span><br><span class="line">        x /= <span class="number">10</span>;</span><br><span class="line">        re *= <span class="number">10</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> re;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">go_dp</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">2</span>; i&lt;=M; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span>(!vis[i])</span><br><span class="line">        &#123;</span><br><span class="line">            dp[i] = i;</span><br><span class="line">            <span class="type">int</span> mul = <span class="built_in">getmul</span>(i);</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">2</span>; i*j&lt;=M; j++)</span><br><span class="line">            &#123;</span><br><span class="line">                vis[i*j] = <span class="literal">true</span>;</span><br><span class="line">                <span class="type">int</span> cnt = <span class="number">0</span>;</span><br><span class="line">                LL tt = i*j;</span><br><span class="line">                <span class="keyword">while</span>(tt % i == <span class="number">0</span>)</span><br><span class="line">                &#123;</span><br><span class="line">                    cnt += <span class="number">1</span>;</span><br><span class="line">                    tt /= i;</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">for</span>(<span class="type">int</span> k=<span class="number">0</span>; k&lt;cnt; k++)</span><br><span class="line">                &#123;</span><br><span class="line">                    dp[i*j] = (dp[i*j] * mul + i) % mod;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    LL ans = <span class="number">0</span>;</span><br><span class="line">    std::cin &gt;&gt; M;</span><br><span class="line">    <span class="built_in">go_dp</span>();</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">2</span>; i&lt;=M; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        ans = (ans+dp[i])%mod;</span><br><span class="line">    &#125;</span><br><span class="line">    std::cout &lt;&lt; ans;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>抄欧拉模板的话好像数字的排列方式有问题</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E7%AD%9B%E6%B3%95-%E7%B4%A0%E6%95%B0/" data-id="cl2uhoedo005we4j3dcve4gyj" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E6%95%B0%E8%AE%BA/" rel="tag">数论</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-随机森林的应用简例" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E9%9A%8F%E6%9C%BA%E6%A3%AE%E6%9E%97%E7%9A%84%E5%BA%94%E7%94%A8%E7%AE%80%E4%BE%8B/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E9%9A%8F%E6%9C%BA%E6%A3%AE%E6%9E%97%E7%9A%84%E5%BA%94%E7%94%A8%E7%AE%80%E4%BE%8B/">随机森林的应用简例.md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E6%95%99%E7%BB%83%E6%88%91%E6%83%B3%E5%AD%A6%E6%8C%82%E8%BE%B9%E8%BA%B2%E7%89%9B/">教练我想学挂边躲牛</a>,<a class="article-category-link" href="/categories/%E6%95%99%E7%BB%83%E6%88%91%E6%83%B3%E5%AD%A6%E6%8C%82%E8%BE%B9%E8%BA%B2%E7%89%9B/%E7%9E%8E%E5%AD%A6%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0/">瞎学机器学习</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<p>用jupyter lab 做的 太多了懒得排版</p>
<p>​</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br><span class="line">202</span><br><span class="line">203</span><br><span class="line">204</span><br><span class="line">205</span><br><span class="line">206</span><br><span class="line">207</span><br><span class="line">208</span><br><span class="line">209</span><br><span class="line">210</span><br><span class="line">211</span><br><span class="line">212</span><br><span class="line">213</span><br><span class="line">214</span><br><span class="line">215</span><br><span class="line">216</span><br><span class="line">217</span><br><span class="line">218</span><br><span class="line">219</span><br><span class="line">220</span><br><span class="line">221</span><br><span class="line">222</span><br><span class="line">223</span><br></pre></td><td class="code"><pre><span class="line">%matplotlib inline</span><br><span class="line"><span class="keyword">import</span> numpy <span class="keyword">as</span> np</span><br><span class="line"><span class="keyword">import</span> pandas <span class="keyword">as</span> pd</span><br><span class="line"><span class="keyword">from</span> sklearn.model_selection <span class="keyword">import</span> GridSearchCV</span><br><span class="line"><span class="keyword">from</span> sklearn.ensemble <span class="keyword">import</span> RandomForestClassifier</span><br><span class="line">df_t = pd.read_excel(<span class="string">r&#x27;D:\EdgeDownloadPlace\复赛数据集\train.xlsx&#x27;</span>,header=<span class="literal">None</span>)</span><br><span class="line">​</span><br><span class="line"><span class="keyword">import</span> re</span><br><span class="line"><span class="keyword">with</span> <span class="built_in">open</span>(<span class="string">r&#x27;D:\EdgeDownloadPlace\复赛数据集\features.txt&#x27;</span>) <span class="keyword">as</span> f:</span><br><span class="line">    features = re.findall(<span class="string">&#x27;[0-9] (.*)\n&#x27;</span>, f.read())</span><br><span class="line">features.insert(<span class="number">0</span>,<span class="string">&#x27;uid&#x27;</span>)</span><br><span class="line">features.append(<span class="string">&#x27;target&#x27;</span>)</span><br><span class="line">df_t.columns = features</span><br><span class="line">​</span><br><span class="line">df_t = df_t.drop(columns = <span class="string">&#x27;uid&#x27;</span>)</span><br><span class="line">arr_t = df_t.values</span><br><span class="line"><span class="keyword">import</span> time</span><br><span class="line">start_time = time.time()</span><br><span class="line">param_grid = &#123;<span class="string">&#x27;n_estimators&#x27;</span> : np.arange(<span class="number">1</span>,<span class="number">201</span>,<span class="number">40</span>)&#125;</span><br><span class="line">rfc = RandomForestClassifier(random_state = <span class="number">435681971</span></span><br><span class="line">                            ,criterion = <span class="string">&#x27;entropy&#x27;</span>)</span><br><span class="line">gs = GridSearchCV(rfc, param_grid, cv=<span class="number">4</span>)</span><br><span class="line">gs.fit(arr_t[:,:-<span class="number">1</span>],arr_t[:,-<span class="number">1</span>])</span><br><span class="line">​</span><br><span class="line">peak_n_lst = [gs.best_score_, gs.best_params_]</span><br><span class="line">end_time = time.time()</span><br><span class="line">time_span = end_time - start_time</span><br><span class="line">peak_n_lst</span><br><span class="line">​</span><br><span class="line">[<span class="number">0.9373961218836566</span>, &#123;<span class="string">&#x27;n_estimators&#x27;</span>: <span class="number">161</span>&#125;]</span><br><span class="line">time_span</span><br><span class="line"><span class="number">107.33542943000793</span></span><br><span class="line">peak_n = peak_n_lst[<span class="number">1</span>][<span class="string">&#x27;n_estimators&#x27;</span>]</span><br><span class="line">start_time = time.time()</span><br><span class="line">param_grid = &#123;<span class="string">&#x27;n_estimators&#x27;</span> : np.arange(peak_n-<span class="number">20</span>,peak_n+<span class="number">20</span>)&#125;</span><br><span class="line">rfc = RandomForestClassifier(random_state = <span class="number">435681971</span></span><br><span class="line">                            ,criterion = <span class="string">&#x27;entropy&#x27;</span>)</span><br><span class="line">gs = GridSearchCV(rfc, param_grid, cv=<span class="number">4</span>)</span><br><span class="line">gs.fit(arr_t[:,:-<span class="number">1</span>],arr_t[:,-<span class="number">1</span>])</span><br><span class="line">​</span><br><span class="line">peak_n_lst = [gs.best_score_, gs.best_params_]</span><br><span class="line">end_time = time.time()</span><br><span class="line">time_span = end_time - start_time</span><br><span class="line">peak_n = peak_n_lst[<span class="number">1</span>][<span class="string">&#x27;n_estimators&#x27;</span>]</span><br><span class="line">peak_n</span><br><span class="line"><span class="number">170</span></span><br><span class="line">start_time = time.time()</span><br><span class="line">param_grid = &#123;<span class="string">&#x27;max_depth&#x27;</span> : np.arange(<span class="number">1</span>,<span class="number">561</span>//<span class="number">2</span>,<span class="number">30</span>)&#125;</span><br><span class="line">rfc = RandomForestClassifier(random_state = <span class="number">435681971</span></span><br><span class="line">                            ,n_estimators = peak_n</span><br><span class="line">                            ,criterion = <span class="string">&#x27;entropy&#x27;</span>)</span><br><span class="line">gs = GridSearchCV(rfc, param_grid, cv=<span class="number">4</span>)</span><br><span class="line">gs.fit(arr_t[:,:-<span class="number">1</span>],arr_t[:,-<span class="number">1</span>])</span><br><span class="line">​</span><br><span class="line">peak_depth_lst = [gs.best_score_, gs.best_params_]</span><br><span class="line">end_time = time.time()</span><br><span class="line">time_span = end_time - start_time</span><br><span class="line">peak_depth_lst</span><br><span class="line">[<span class="number">0.9386426592797784</span>, &#123;<span class="string">&#x27;max_depth&#x27;</span>: <span class="number">31</span>&#125;]</span><br><span class="line">time_span</span><br><span class="line"><span class="number">407.307009935379</span></span><br><span class="line">peak_depth = peak_depth_lst[<span class="number">1</span>][<span class="string">&#x27;max_depth&#x27;</span>]</span><br><span class="line">peak_depth</span><br><span class="line"><span class="number">31</span></span><br><span class="line">start_time = time.time()</span><br><span class="line">param_grid = &#123;<span class="string">&#x27;max_depth&#x27;</span> : np.arange(peak_depth-<span class="number">20</span>, peak_depth+<span class="number">30</span>)&#125;</span><br><span class="line">rfc = RandomForestClassifier(random_state = <span class="number">435681971</span></span><br><span class="line">                            ,n_estimators = peak_n</span><br><span class="line">                            ,criterion = <span class="string">&#x27;entropy&#x27;</span>)</span><br><span class="line">gs = GridSearchCV(rfc, param_grid, cv=<span class="number">4</span>)</span><br><span class="line">gs.fit(arr_t[:,:-<span class="number">1</span>],arr_t[:,-<span class="number">1</span>])</span><br><span class="line">​</span><br><span class="line">peak_depth_lst = [gs.best_score_, gs.best_params_]</span><br><span class="line">end_time = time.time()</span><br><span class="line">time_span = end_time - start_time</span><br><span class="line">peak_depth_lst</span><br><span class="line">[<span class="number">0.9393351800554016</span>, &#123;<span class="string">&#x27;max_depth&#x27;</span>: <span class="number">14</span>&#125;]</span><br><span class="line">time_span/<span class="number">60</span></span><br><span class="line">​</span><br><span class="line"><span class="number">31.484332279364267</span></span><br><span class="line">peak_depth = peak_depth_lst[<span class="number">1</span>][<span class="string">&#x27;max_depth&#x27;</span>]</span><br><span class="line">peak_depth</span><br><span class="line"><span class="number">14</span></span><br><span class="line">start_time = time.time()</span><br><span class="line">param_grid = &#123;<span class="string">&#x27;min_samples_split&#x27;</span> : np.arange(<span class="number">2</span>,<span class="number">125</span>,<span class="number">30</span>)&#125;</span><br><span class="line">rfc = RandomForestClassifier(random_state = <span class="number">435681971</span></span><br><span class="line">                            ,n_estimators = peak_n</span><br><span class="line">                            ,max_depth = peak_depth</span><br><span class="line">                            ,criterion = <span class="string">&#x27;entropy&#x27;</span>)</span><br><span class="line">gs = GridSearchCV(rfc, param_grid, cv=<span class="number">4</span>)</span><br><span class="line">gs.fit(arr_t[:,:-<span class="number">1</span>],arr_t[:,-<span class="number">1</span>])</span><br><span class="line">​</span><br><span class="line">peak_depth_lst = [gs.best_score_, gs.best_params_]</span><br><span class="line">end_time = time.time()</span><br><span class="line">time_span = end_time - start_time</span><br><span class="line">time_span/<span class="number">60</span></span><br><span class="line"><span class="number">3.157407291730245</span></span><br><span class="line"><span class="comment">#peak_depth_lst 上面忘记换名字了</span></span><br><span class="line">peak_minss = peak_depth_lst[<span class="number">1</span>][<span class="string">&#x27;min_samples_split&#x27;</span>]</span><br><span class="line">peak_minss</span><br><span class="line"><span class="number">2</span></span><br><span class="line">start_time = time.time()</span><br><span class="line">param_grid = &#123;<span class="string">&#x27;min_samples_split&#x27;</span> : np.arange(<span class="number">2</span>,<span class="number">30</span>)&#125;</span><br><span class="line">rfc = RandomForestClassifier(random_state = <span class="number">435681971</span></span><br><span class="line">                            ,n_estimators = peak_n</span><br><span class="line">                            ,max_depth = peak_depth</span><br><span class="line">                            ,criterion = <span class="string">&#x27;entropy&#x27;</span>)</span><br><span class="line">gs = GridSearchCV(rfc, param_grid, cv=<span class="number">4</span>)</span><br><span class="line">gs.fit(arr_t[:,:-<span class="number">1</span>],arr_t[:,-<span class="number">1</span>])</span><br><span class="line">​</span><br><span class="line">peak_depth_lst = [gs.best_score_, gs.best_params_]</span><br><span class="line">end_time = time.time()</span><br><span class="line">time_span = end_time - start_time</span><br><span class="line">time_span</span><br><span class="line"><span class="number">1053.7646670341492</span></span><br><span class="line">peak_depth_lst</span><br><span class="line">[<span class="number">0.9393351800554016</span>, &#123;<span class="string">&#x27;min_samples_split&#x27;</span>: <span class="number">2</span>&#125;]</span><br><span class="line">peak_minss = peak_depth_lst[<span class="number">1</span>][<span class="string">&#x27;min_samples_split&#x27;</span>]</span><br><span class="line">peak_minss</span><br><span class="line"><span class="number">2</span></span><br><span class="line"><span class="keyword">import</span> matplotlib.pyplot <span class="keyword">as</span> plt</span><br><span class="line">peak_n = <span class="number">170</span></span><br><span class="line">peak_depth = <span class="number">14</span></span><br><span class="line">peak_minss = <span class="number">3</span></span><br><span class="line"><span class="comment">#rfc = RandomForestClassifier(random_state = 435681971</span></span><br><span class="line"><span class="comment">#                            ,n_estimators = peak_n</span></span><br><span class="line"><span class="comment">#                            ,max_depth = peak_depth</span></span><br><span class="line"><span class="comment">#                            ,min_samples_split = peak_minss</span></span><br><span class="line"><span class="comment">#                            ,oob_score = True)</span></span><br><span class="line"><span class="comment">#rfc.fit(arr_t[:,:-1],arr_t[:,-1])</span></span><br><span class="line"><span class="comment">#rfc.oob_score_</span></span><br><span class="line"><span class="comment">#plt.figure(figsize = [20,5])</span></span><br><span class="line">​</span><br><span class="line"><span class="comment">#score_lst=[]</span></span><br><span class="line"><span class="comment">#for i in range(30):</span></span><br><span class="line"><span class="comment">#    rfc = RandomForestClassifier(#random_state = 435681971</span></span><br><span class="line"><span class="comment">#                                n_estimators = peak_n</span></span><br><span class="line"><span class="comment">#                                ,max_depth = peak_depth</span></span><br><span class="line"><span class="comment">#                                ,min_samples_split = peak_minss</span></span><br><span class="line"><span class="comment">#                                ,oob_score = True)</span></span><br><span class="line"><span class="comment">#    rfc.fit(arr_t[:,:-1],arr_t[:,-1])</span></span><br><span class="line"><span class="comment">#    score_lst.append(rfc.oob_score_)</span></span><br><span class="line"><span class="comment">#plt.plot(range(1,31),score_lst)</span></span><br><span class="line">​</span><br><span class="line">score_lst=[]</span><br><span class="line"><span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">30</span>):</span><br><span class="line">    rfc = RandomForestClassifier(<span class="comment">#random_state = 435681971</span></span><br><span class="line">                                n_estimators = peak_n</span><br><span class="line">                                ,max_depth = peak_depth</span><br><span class="line">                                ,min_samples_split = peak_minss</span><br><span class="line">                                ,oob_score = <span class="literal">True</span></span><br><span class="line">                                ,criterion = <span class="string">&#x27;entropy&#x27;</span>)</span><br><span class="line">    rfc.fit(arr_t[:,:-<span class="number">1</span>],arr_t[:,-<span class="number">1</span>])</span><br><span class="line">    score_lst.append(rfc.oob_score_)</span><br><span class="line">plt.plot(<span class="built_in">range</span>(<span class="number">1</span>,<span class="number">31</span>),score_lst,color = <span class="string">&#x27;red&#x27;</span>)</span><br><span class="line">​</span><br><span class="line">plt.show()   </span><br><span class="line"></span><br><span class="line">plt.figure(figsize = [<span class="number">15</span>,<span class="number">6</span>])</span><br><span class="line">plt.plot(<span class="built_in">range</span>(<span class="number">1</span>,<span class="number">31</span>),score_lst,color = <span class="string">&#x27;red&#x27;</span>)</span><br><span class="line">plt.show()</span><br><span class="line"></span><br><span class="line"><span class="keyword">while</span> <span class="literal">True</span>:</span><br><span class="line">    rfc = RandomForestClassifier(<span class="comment">#random_state = 435681971</span></span><br><span class="line">                                n_estimators = peak_n</span><br><span class="line">                                ,max_depth = peak_depth</span><br><span class="line">                                ,min_samples_split = peak_minss</span><br><span class="line">                                ,oob_score = <span class="literal">True</span></span><br><span class="line">                                ,criterion = <span class="string">&#x27;entropy&#x27;</span>)</span><br><span class="line">    rfc.fit(arr_t[:,:-<span class="number">1</span>],arr_t[:,-<span class="number">1</span>])</span><br><span class="line">    <span class="keyword">if</span> rfc.oob_score_ &gt; <span class="number">0.978</span>:</span><br><span class="line">        <span class="keyword">break</span></span><br><span class="line">df_a = pd.read_excel(<span class="string">r&#x27;D:\EdgeDownloadPlace\复赛数据集\test.xlsx&#x27;</span>,header=<span class="literal">None</span>)</span><br><span class="line">​</span><br><span class="line">df_a.columns = features[:-<span class="number">1</span>]</span><br><span class="line">​</span><br><span class="line">df_a = df_a.drop(columns= <span class="string">&#x27;uid&#x27;</span>)</span><br><span class="line">df_a</span><br><span class="line">tBodyAcc-mean()-X	tBodyAcc-mean()-Y	tBodyAcc-mean()-Z	tBodyAcc-std()-X	tBodyAcc-std()-Y	tBodyAcc-std()-Z	tBodyAcc-mad()-X	tBodyAcc-mad()-Y	tBodyAcc-mad()-Z	tBodyAcc-<span class="built_in">max</span>()-X	...	fBodyBodyGyroJerkMag-meanFreq()	fBodyBodyGyroJerkMag-skewness()	fBodyBodyGyroJerkMag-kurtosis()	angle(tBodyAccMean,gravity)	angle(tBodyAccJerkMean),gravityMean)	angle(tBodyGyroMean,gravityMean)	angle(tBodyGyroJerkMean,gravityMean)	angle(X,gravityMean)	angle(Y,gravityMean)	angle(Z,gravityMean)</span><br><span class="line"><span class="number">0</span>	<span class="number">0.278</span>	-<span class="number">0.01640</span>	-<span class="number">0.1240</span>	-<span class="number">0.998</span>	-<span class="number">0.9750</span>	-<span class="number">0.960</span>	-<span class="number">0.999</span>	-<span class="number">0.9750</span>	-<span class="number">0.958</span>	-<span class="number">0.9430</span>	...	<span class="number">0.1580</span>	-<span class="number">0.5950</span>	-<span class="number">0.861</span>	<span class="number">0.0535</span>	-<span class="number">0.00743</span>	-<span class="number">0.733</span>	<span class="number">0.7040</span>	-<span class="number">0.845</span>	<span class="number">0.180</span>	-<span class="number">0.0543</span></span><br><span class="line"><span class="number">1</span>	<span class="number">0.281</span>	-<span class="number">0.00996</span>	-<span class="number">0.1060</span>	-<span class="number">0.995</span>	-<span class="number">0.9730</span>	-<span class="number">0.986</span>	-<span class="number">0.995</span>	-<span class="number">0.9740</span>	-<span class="number">0.986</span>	-<span class="number">0.9400</span>	...	<span class="number">0.2670</span>	<span class="number">0.3400</span>	<span class="number">0.140</span>	-<span class="number">0.0206</span>	-<span class="number">0.12800</span>	-<span class="number">0.483</span>	-<span class="number">0.0707</span>	-<span class="number">0.848</span>	<span class="number">0.190</span>	-<span class="number">0.0344</span></span><br><span class="line"><span class="number">2</span>	<span class="number">0.277</span>	-<span class="number">0.01470</span>	-<span class="number">0.1070</span>	-<span class="number">0.999</span>	-<span class="number">0.9910</span>	-<span class="number">0.993</span>	-<span class="number">0.999</span>	-<span class="number">0.9910</span>	-<span class="number">0.992</span>	-<span class="number">0.9430</span>	...	<span class="number">0.7400</span>	-<span class="number">0.5640</span>	-<span class="number">0.766</span>	<span class="number">0.1060</span>	-<span class="number">0.09030</span>	-<span class="number">0.132</span>	<span class="number">0.4990</span>	-<span class="number">0.850</span>	<span class="number">0.189</span>	-<span class="number">0.0351</span></span><br><span class="line"><span class="number">3</span>	<span class="number">0.279</span>	-<span class="number">0.02300</span>	-<span class="number">0.1220</span>	-<span class="number">0.997</span>	-<span class="number">0.9750</span>	-<span class="number">0.983</span>	-<span class="number">0.997</span>	-<span class="number">0.9730</span>	-<span class="number">0.984</span>	-<span class="number">0.9420</span>	...	<span class="number">0.6620</span>	-<span class="number">0.7820</span>	-<span class="number">0.954</span>	-<span class="number">0.1220</span>	-<span class="number">0.02910</span>	-<span class="number">0.013</span>	-<span class="number">0.0569</span>	-<span class="number">0.761</span>	<span class="number">0.263</span>	<span class="number">0.0242</span></span><br><span class="line"><span class="number">4</span>	<span class="number">0.280</span>	-<span class="number">0.01390</span>	-<span class="number">0.1060</span>	-<span class="number">0.998</span>	-<span class="number">0.9880</span>	-<span class="number">0.990</span>	-<span class="number">0.998</span>	-<span class="number">0.9880</span>	-<span class="number">0.992</span>	-<span class="number">0.9420</span>	...	<span class="number">0.4290</span>	-<span class="number">0.3290</span>	-<span class="number">0.597</span>	-<span class="number">0.0283</span>	<span class="number">0.09240</span>	-<span class="number">0.822</span>	<span class="number">0.3680</span>	-<span class="number">0.759</span>	<span class="number">0.264</span>	<span class="number">0.0297</span></span><br><span class="line">...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...</span><br><span class="line"><span class="number">3074</span>	<span class="number">0.231</span>	-<span class="number">0.04230</span>	-<span class="number">0.0899</span>	-<span class="number">0.309</span>	-<span class="number">0.0791</span>	-<span class="number">0.152</span>	-<span class="number">0.391</span>	-<span class="number">0.0870</span>	-<span class="number">0.257</span>	<span class="number">0.0562</span>	...	-<span class="number">0.0310</span>	-<span class="number">0.1390</span>	-<span class="number">0.589</span>	<span class="number">0.2730</span>	<span class="number">0.85600</span>	-<span class="number">0.962</span>	<span class="number">0.9530</span>	-<span class="number">0.657</span>	<span class="number">0.276</span>	<span class="number">0.1770</span></span><br><span class="line"><span class="number">3075</span>	<span class="number">0.357</span>	-<span class="number">0.04460</span>	-<span class="number">0.1300</span>	-<span class="number">0.314</span>	-<span class="number">0.0556</span>	-<span class="number">0.173</span>	-<span class="number">0.386</span>	-<span class="number">0.0575</span>	-<span class="number">0.217</span>	<span class="number">0.0262</span>	...	<span class="number">0.0168</span>	-<span class="number">0.1630</span>	-<span class="number">0.593</span>	-<span class="number">0.7110</span>	-<span class="number">0.06120</span>	-<span class="number">0.706</span>	<span class="number">0.0646</span>	-<span class="number">0.660</span>	<span class="number">0.274</span>	<span class="number">0.1760</span></span><br><span class="line"><span class="number">3076</span>	<span class="number">0.284</span>	-<span class="number">0.00796</span>	-<span class="number">0.1190</span>	-<span class="number">0.309</span>	-<span class="number">0.0804</span>	-<span class="number">0.211</span>	-<span class="number">0.369</span>	-<span class="number">0.0971</span>	-<span class="number">0.301</span>	-<span class="number">0.1170</span>	...	-<span class="number">0.1100</span>	<span class="number">0.0245</span>	-<span class="number">0.393</span>	-<span class="number">0.0761</span>	-<span class="number">0.23900</span>	<span class="number">0.960</span>	<span class="number">0.0866</span>	-<span class="number">0.657</span>	<span class="number">0.272</span>	<span class="number">0.1830</span></span><br><span class="line"><span class="number">3077</span>	<span class="number">0.207</span>	<span class="number">0.02460</span>	-<span class="number">0.1040</span>	-<span class="number">0.365</span>	-<span class="number">0.1690</span>	-<span class="number">0.216</span>	-<span class="number">0.449</span>	-<span class="number">0.1860</span>	-<span class="number">0.326</span>	-<span class="number">0.1760</span>	...	-<span class="number">0.2140</span>	-<span class="number">0.3520</span>	-<span class="number">0.734</span>	<span class="number">0.5350</span>	-<span class="number">0.25700</span>	<span class="number">0.927</span>	-<span class="number">0.0843</span>	-<span class="number">0.657</span>	<span class="number">0.267</span>	<span class="number">0.1880</span></span><br><span class="line"><span class="number">3078</span>	<span class="number">0.331</span>	-<span class="number">0.06400</span>	-<span class="number">0.1170</span>	-<span class="number">0.068</span>	<span class="number">0.1560</span>	-<span class="number">0.317</span>	-<span class="number">0.149</span>	<span class="number">0.0701</span>	-<span class="number">0.291</span>	<span class="number">0.4120</span>	...	-<span class="number">0.0214</span>	-<span class="number">0.0863</span>	-<span class="number">0.468</span>	-<span class="number">0.3510</span>	-<span class="number">0.33600</span>	<span class="number">0.967</span>	-<span class="number">0.7150</span>	-<span class="number">0.810</span>	<span class="number">0.185</span>	<span class="number">0.1210</span></span><br><span class="line"><span class="number">3079</span> rows × <span class="number">561</span> columns</span><br><span class="line"></span><br><span class="line">arr_a = df_a.values</span><br><span class="line">arr_a</span><br><span class="line">array([[ <span class="number">0.278</span>  , -<span class="number">0.0164</span> , -<span class="number">0.124</span>  , ..., -<span class="number">0.845</span>  ,  <span class="number">0.18</span>   , -<span class="number">0.0543</span> ],</span><br><span class="line">       [ <span class="number">0.281</span>  , -<span class="number">0.00996</span>, -<span class="number">0.106</span>  , ..., -<span class="number">0.848</span>  ,  <span class="number">0.19</span>   , -<span class="number">0.0344</span> ],</span><br><span class="line">       [ <span class="number">0.277</span>  , -<span class="number">0.0147</span> , -<span class="number">0.107</span>  , ..., -<span class="number">0.85</span>   ,  <span class="number">0.189</span>  , -<span class="number">0.0351</span> ],</span><br><span class="line">       ...,</span><br><span class="line">       [ <span class="number">0.284</span>  , -<span class="number">0.00796</span>, -<span class="number">0.119</span>  , ..., -<span class="number">0.657</span>  ,  <span class="number">0.272</span>  ,  <span class="number">0.183</span>  ],</span><br><span class="line">       [ <span class="number">0.207</span>  ,  <span class="number">0.0246</span> , -<span class="number">0.104</span>  , ..., -<span class="number">0.657</span>  ,  <span class="number">0.267</span>  ,  <span class="number">0.188</span>  ],</span><br><span class="line">       [ <span class="number">0.331</span>  , -<span class="number">0.064</span>  , -<span class="number">0.117</span>  , ..., -<span class="number">0.81</span>   ,  <span class="number">0.185</span>  ,  <span class="number">0.121</span>  ]])</span><br><span class="line">answer = rfc.predict(arr_a).astype(np.int8).tolist()</span><br><span class="line"><span class="built_in">len</span>(answer)</span><br><span class="line"><span class="number">3079</span></span><br><span class="line">answer_df = pd.DataFrame(answer)</span><br><span class="line">answer_df</span><br><span class="line"><span class="number">0</span></span><br><span class="line"><span class="number">0</span>	<span class="number">5</span></span><br><span class="line"><span class="number">1</span>	<span class="number">5</span></span><br><span class="line"><span class="number">2</span>	<span class="number">5</span></span><br><span class="line"><span class="number">3</span>	<span class="number">5</span></span><br><span class="line"><span class="number">4</span>	<span class="number">5</span></span><br><span class="line">...	...</span><br><span class="line"><span class="number">3074</span>	<span class="number">2</span></span><br><span class="line"><span class="number">3075</span>	<span class="number">2</span></span><br><span class="line"><span class="number">3076</span>	<span class="number">2</span></span><br><span class="line"><span class="number">3077</span>	<span class="number">2</span></span><br><span class="line"><span class="number">3078</span>	<span class="number">3</span></span><br><span class="line"><span class="number">3079</span> rows × <span class="number">1</span> columns</span><br><span class="line"></span><br><span class="line">answer_df.to_excel(<span class="string">r&#x27;D:\EdgeDownloadPlace\复赛数据集\ANS\20201104try.xlsx&#x27;</span>)</span><br><span class="line"><span class="built_in">print</span>(<span class="string">&#x27;ok&#x27;</span>)</span><br><span class="line">ok</span><br></pre></td></tr></table></figure>
<p>​</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E9%9A%8F%E6%9C%BA%E6%A3%AE%E6%9E%97%E7%9A%84%E5%BA%94%E7%94%A8%E7%AE%80%E4%BE%8B/" data-id="cl2uhoedp005ze4j3gj4jdd1r" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0/" rel="tag">机器学习</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E9%9A%8F%E6%9C%BA%E6%A3%AE%E6%9E%97/" rel="tag">随机森林</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-记忆化搜索（貌似，不太清楚是不是，自己摸索题的时候猜了一个） L3-025 那就别担心了 (30 分)" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E8%AE%B0%E5%BF%86%E5%8C%96%E6%90%9C%E7%B4%A2%EF%BC%88%E8%B2%8C%E4%BC%BC%EF%BC%8C%E4%B8%8D%E5%A4%AA%E6%B8%85%E6%A5%9A%E6%98%AF%E4%B8%8D%E6%98%AF%EF%BC%8C%E8%87%AA%E5%B7%B1%E6%91%B8%E7%B4%A2%E9%A2%98%E7%9A%84%E6%97%B6%E5%80%99%E7%8C%9C%E4%BA%86%E4%B8%80%E4%B8%AA%EF%BC%89%20L3-025%20%E9%82%A3%E5%B0%B1%E5%88%AB%E6%8B%85%E5%BF%83%E4%BA%86%20(30%20%E5%88%86)/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%E8%AE%B0%E5%BF%86%E5%8C%96%E6%90%9C%E7%B4%A2%EF%BC%88%E8%B2%8C%E4%BC%BC%EF%BC%8C%E4%B8%8D%E5%A4%AA%E6%B8%85%E6%A5%9A%E6%98%AF%E4%B8%8D%E6%98%AF%EF%BC%8C%E8%87%AA%E5%B7%B1%E6%91%B8%E7%B4%A2%E9%A2%98%E7%9A%84%E6%97%B6%E5%80%99%E7%8C%9C%E4%BA%86%E4%B8%80%E4%B8%AA%EF%BC%89%20L3-025%20%E9%82%A3%E5%B0%B1%E5%88%AB%E6%8B%85%E5%BF%83%E4%BA%86%20(30%20%E5%88%86)/">记忆化搜索（貌似，不太清楚是不是，自己摸索题的时候猜了一个） L3-025 那就别担心了 (30 分).md</a>
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/%E6%90%9C%E7%B4%A2/">搜索</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<h2 id="题目"><a class="markdownIt-Anchor" href="#题目"></a> 题目</h2>
<p>&lt;<a target="_blank" rel="noopener" href="https://pintia.cn/problem-">https://pintia.cn/problem-</a><br />
sets/994805046380707840/problems/1336215880692482060&gt;<br />
下图转自“英式没品笑话百科”的新浪微博 —— 所以无论有没有遇到难题，其实都不用担心。<br />
![在这里插入图片描述](https://img-<br />
<a target="_blank" rel="noopener" href="http://blog.csdnimg.cn/img_convert/c391ed5f2575c951739264f1eb9226e7.png#pic_center">blog.csdnimg.cn/img_convert/c391ed5f2575c951739264f1eb9226e7.png#pic_center</a>)<br />
博主将这种逻辑推演称为“逻辑自洽”，即从某个命题出发的所有推理路径都会将结论引导到同一个最终命题（开玩笑的，千万别以为这是真正的逻辑自洽的定义……）。现给定一个更为复杂的逻辑推理图，本题就请你检查从一个给定命题到另一个命题的推理是否是“逻辑自洽”的，以及存在多少种不同的推理路径。例如上图，从“你遇到难题了吗？”到“那就别担心了”就是一种“逻辑自洽”的推理，一共有<br />
3 条不同的推理路径。</p>
<p>输入格式：<br />
输入首先在一行中给出两个正整数 N（1&lt;N≤500）和 M，分别为命题个数和推理个数。这里我们假设命题从 1 到 N 编号。</p>
<p>接下来 M 行，每行给出一对命题之间的推理关系，即两个命题的编号 S1 S2，表示可以从 S1 推出<br />
S2。题目保证任意两命题之间只存在最多一种推理关系，且任一命题不能循环自证（即从该命题出发推出该命题自己）。</p>
<p>最后一行给出待检验的两个命题的编号 A B。</p>
<p>输出格式：<br />
在一行中首先输出从 A 到 B 有多少种不同的推理路径，然后输出 Yes 如果推理是“逻辑自洽”的，或 No 如果不是。</p>
<p>题目保证输出数据不超过 1e​9。</p>
<p>输入样例 1：<br />
7 8<br />
7 6<br />
7 4<br />
6 5<br />
4 1<br />
5 2<br />
5 3<br />
2 1<br />
3 1<br />
7 1<br />
输出样例 1：<br />
3 Yes<br />
输入样例 2：<br />
7 8<br />
7 6<br />
7 4<br />
6 5<br />
4 1<br />
5 2<br />
5 3<br />
6 1<br />
3 1<br />
7 1<br />
输出样例 2：<br />
3 No</p>
<h2 id="代码"><a class="markdownIt-Anchor" href="#代码"></a> 代码</h2>
<p>一开始暴力dfs最后一个样例过不了，不是开了一个vis数组记录。刚开始瞎记录，把找到终点的路径标记为true，但是会发生路径数与最终答案不同的错误。后来发现vis数组应该开int类型。然后继续摸索。<br />
ac后总结了一下，vis数组记录的是当前节点通往终点的路径条数。<br />
代码：</p>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdlib&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;map&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;set&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">505</span>, M = <span class="number">250005</span>;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> head[N],dout[N],vis[N];</span><br><span class="line"><span class="type">int</span> idx;</span><br><span class="line"><span class="type">int</span> n,m,u,v,to,zero;</span><br><span class="line"><span class="type">int</span> ans;</span><br><span class="line"></span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">Edge</span>&#123;</span><br><span class="line">   <span class="type">int</span> to,nxt;</span><br><span class="line">&#125;edge[M];</span><br></pre></td></tr></table></figure>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">int</span> <span class="title">dfs</span><span class="params">(<span class="type">int</span> x)</span></span>&#123;</span><br><span class="line">   <span class="keyword">if</span>(vis[x]) &#123;</span><br><span class="line">      ans += vis[x];</span><br><span class="line">      <span class="keyword">return</span> vis[x];</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">if</span>(!dout[x])&#123;</span><br><span class="line">      zero += <span class="number">1</span>;</span><br><span class="line">      dout[x] = <span class="number">-1</span>;</span><br><span class="line">      <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=head[x]; i!=<span class="number">-1</span>; i= edge[i].nxt)&#123;</span><br><span class="line">      to = edge[i].to;</span><br><span class="line">      vis[x] += <span class="built_in">dfs</span>(to);</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">return</span> vis[x];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">   idx = <span class="number">-1</span>;</span><br><span class="line">   <span class="built_in">memset</span>(head,<span class="number">-1</span>,<span class="built_in">sizeof</span>(head));</span><br><span class="line">   <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;n,&amp;m);</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;m; i++)&#123;</span><br><span class="line">      <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;u,&amp;v);</span><br><span class="line">      edge[++idx] = &#123;v,head[u]&#125;; head[u] = idx;</span><br><span class="line">      dout[u] += <span class="number">1</span>;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;u,&amp;v);</span><br><span class="line">   vis[v] = <span class="number">1</span>;</span><br><span class="line">   <span class="built_in">dfs</span>(u);</span><br><span class="line">   <span class="built_in">printf</span>(<span class="string">&quot;%d %s&quot;</span>,ans,(!zero) ? <span class="string">&quot;Yes&quot;</span> : <span class="string">&quot;No&quot;</span>);</span><br><span class="line">   <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E8%AE%B0%E5%BF%86%E5%8C%96%E6%90%9C%E7%B4%A2%EF%BC%88%E8%B2%8C%E4%BC%BC%EF%BC%8C%E4%B8%8D%E5%A4%AA%E6%B8%85%E6%A5%9A%E6%98%AF%E4%B8%8D%E6%98%AF%EF%BC%8C%E8%87%AA%E5%B7%B1%E6%91%B8%E7%B4%A2%E9%A2%98%E7%9A%84%E6%97%B6%E5%80%99%E7%8C%9C%E4%BA%86%E4%B8%80%E4%B8%AA%EF%BC%89%20L3-025%20%E9%82%A3%E5%B0%B1%E5%88%AB%E6%8B%85%E5%BF%83%E4%BA%86%20(30%20%E5%88%86)/" data-id="cl2uhoedq0064e4j38ruwcohr" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/DFS/" rel="tag">DFS</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-（强行算法）对2019点美赛D题极端化的算法探讨、设计与遇到的问题（未完,但可能也到此为止）" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%EF%BC%88%E5%BC%BA%E8%A1%8C%E7%AE%97%E6%B3%95%EF%BC%89%E5%AF%B92019%E7%82%B9%E7%BE%8E%E8%B5%9BD%E9%A2%98%E6%9E%81%E7%AB%AF%E5%8C%96%E7%9A%84%E7%AE%97%E6%B3%95%E6%8E%A2%E8%AE%A8%E3%80%81%E8%AE%BE%E8%AE%A1%E4%B8%8E%E9%81%87%E5%88%B0%E7%9A%84%E9%97%AE%E9%A2%98%EF%BC%88%E6%9C%AA%E5%AE%8C,%E4%BD%86%E5%8F%AF%E8%83%BD%E4%B9%9F%E5%88%B0%E6%AD%A4%E4%B8%BA%E6%AD%A2%EF%BC%89/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/%EF%BC%88%E5%BC%BA%E8%A1%8C%E7%AE%97%E6%B3%95%EF%BC%89%E5%AF%B92019%E7%82%B9%E7%BE%8E%E8%B5%9BD%E9%A2%98%E6%9E%81%E7%AB%AF%E5%8C%96%E7%9A%84%E7%AE%97%E6%B3%95%E6%8E%A2%E8%AE%A8%E3%80%81%E8%AE%BE%E8%AE%A1%E4%B8%8E%E9%81%87%E5%88%B0%E7%9A%84%E9%97%AE%E9%A2%98%EF%BC%88%E6%9C%AA%E5%AE%8C,%E4%BD%86%E5%8F%AF%E8%83%BD%E4%B9%9F%E5%88%B0%E6%AD%A4%E4%B8%BA%E6%AD%A2%EF%BC%89/">（强行算法）对2019点美赛D题极端化的算法探讨、设计与遇到的问题（未完,但可能也到此为止）.md</a>
    </h1>
  

        <div>
          
          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<h4 id="卢浮宫-某建筑疏散问题-时序无向图"><a class="markdownIt-Anchor" href="#卢浮宫-某建筑疏散问题-时序无向图"></a> <s>卢浮宫</s> 某建筑疏散问题 <s>时序无向图？</s></h4>
<p>不考虑残疾人，不考虑工作人员，不考虑一切麻烦事。只考虑一群正常人走出建筑，怎样最快。<br />
核心思路是随着时间的增加不断扩大每个出口的覆盖范围，让出口在覆盖范围内“找人”代表路线的规划</p>
<h4 id="0-铺垫定义"><a class="markdownIt-Anchor" href="#0-铺垫定义"></a> 0. 铺垫定义</h4>
<p>假设某建筑有好几层，层与层之间有若干通道连接，将这些通道定义为 <strong>窄道</strong> （如楼梯），出口有若干个，可以存在于任意一层，出口与外界之间也存在<br />
<strong>窄道</strong> （如门）（若人是源源不断的，则通过门和通过楼梯所需的平均时间近似相等）</p>
<h4 id="1定义-单位时间"><a class="markdownIt-Anchor" href="#1定义-单位时间"></a> 1.定义 单位时间</h4>
<p>选一个合适的时间长度当 <strong>单位时间</strong></p>
<h4 id="2定义-单位距离"><a class="markdownIt-Anchor" href="#2定义-单位距离"></a> 2.定义 单位距离</h4>
<p><strong>单位时间</strong> 内人按某个速度匀速行进的距离作为 <strong>单位距离</strong> （eg：走楼梯和走平地在 <strong>单位时间</strong> 内走过的距离可能不同，但他们同为<br />
<strong>单位距离</strong> ，即只算时间），单位时间内能通过 <strong>窄道</strong> 的最大人数称为该出口的 <strong>最大流量</strong></p>
<h4 id="3定义-宽道-窄道"><a class="markdownIt-Anchor" href="#3定义-宽道-窄道"></a> 3.定义 宽道 窄道</h4>
<p>把建筑划分成若干个大小基本相等的多边形（或椭圆形）区域称为 <strong>节点</strong><br />
（对应图数据结构中的点）。相邻的点之间存在通道（对应图数据结构中的边）（大厅或长廊中从一个点到另一个点、连接两个点的楼梯都是通道），若一个通道不是<br />
<strong>窄道</strong> ，则将其定义为 <strong>宽道</strong> ，所有的通道的长度都要求近似符合 <strong>单位距离</strong> 。<br />
默认 <strong>窄道</strong> 人多时会发生拥挤，人流速度受限制，而 <strong>宽道</strong> 不会发生拥挤，人流速度为“无限大”（ <strong>宽道</strong> 可以拥挤，但其拥挤的原因是<br />
<strong>窄道</strong> 限速，所以认为 <strong>宽道</strong> 不拥挤）</p>
<h4 id="4算法思路定义"><a class="markdownIt-Anchor" href="#4算法思路定义"></a> 4.算法思路+定义</h4>
<p>找到所有的出口，刚开始它们的 <strong>时间计数</strong> 为0。<br />
时间计数决定了出口的覆盖范围。（eg：当 <strong>时间计数</strong> 为0时，只有在出口区域一部分人可以逃离建筑；当 <strong>时间计数</strong> 为5时，距离任意一个出口五个<br />
<strong>单位距离</strong> 的人都可以理论上逃离建筑–无视碰撞体积的情况）</p>
<h4 id="5算法思路"><a class="markdownIt-Anchor" href="#5算法思路"></a> 5.算法思路</h4>
<p><strong>循环：</strong><br />
{<br />
1.出口的人数 减少 <strong>最大流量</strong> ，但不能低于0<br />
2. <strong>时间计数</strong> +1<br />
3.若距离出口附近的人数&lt;出口 <strong>最大流量</strong> ：出口点可以在距离自己 <strong>时间计数</strong> 个 <strong>单位距离</strong> 的范围内找人补充人数至 <strong>最大流量</strong><br />
。<br />
注：*递归： * 当出口的覆盖范围中包含 <strong>窄道</strong> 时，应优先从窄道另一端的点找人， <strong>见考虑1</strong> ，进行递归。（若 <strong>窄道</strong><br />
另一端覆盖的范围内存在新的窄道，则这一寻找中优先考虑新的窄道）<br />
}<br />
<strong>终止条件:</strong> <s>所有的点全部覆盖 <strong>且</strong></s> 所有人都逃出生天</p>
<h4 id="a考虑1"><a class="markdownIt-Anchor" href="#a考虑1"></a> a.考虑1</h4>
<p><strong>为什么窄道另一端优先</strong><br />
eg：2层楼疏散，只有一楼有出口，1、2层之间存在若干窄道，出口与外界之间存在若干窄道。姑且把前者称为 <strong>远级窄道</strong> ，后者称为 <strong>近级窄道</strong> 。<br />
显然疏散的最快速度时取决于 <strong>近级窄道</strong> 的。若不给 <strong>远级窄道</strong> 较高的优先级，而恰好所有的 <strong>远级窄道</strong> 的最大流量和&lt;所有<br />
<strong>近级窄道</strong> 的最大流量和，就很可能会出现1楼的人已经疏散完，留下大量的出口，而2楼的人无法及时下来的情况。</p>
<p>这只是一种找到每个通道需要走多少人的办法。当走一条通道的总人数固定，哪里的人先走对时间几乎没有影响。</p>
<h4 id="a问题1"><a class="markdownIt-Anchor" href="#a问题1"></a> A.问题1</h4>
<p>同时涵盖到多条窄道时，如何抉择？(好像遇到坑了，怎么感觉需要花式DP啊）</p>
<h4 id="代码数组模拟数据结构未完成"><a class="markdownIt-Anchor" href="#代码数组模拟数据结构未完成"></a> 代码（数组模拟数据结构）（未完成）</h4>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdlib&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;map&gt;</span></span></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> ll;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> <span class="type">const</span> INF = <span class="number">1e7</span>+<span class="number">7</span>;</span><br><span class="line"><span class="type">int</span> <span class="type">const</span> maxf = <span class="number">10</span>;  <span class="comment">//最大楼层数</span></span><br><span class="line"><span class="type">int</span> <span class="type">const</span> maxn = <span class="number">20</span>;  <span class="comment">//楼层出口最大数目</span></span><br><span class="line"><span class="type">int</span> <span class="type">const</span> maxd = <span class="number">40</span>;  <span class="comment">//区域距离最远楼层出口的最大距离+1</span></span><br><span class="line"><span class="type">int</span> <span class="type">const</span> maxv = <span class="number">1000</span>;<span class="comment">//最多节点个数</span></span><br><span class="line"></span><br><span class="line"><span class="type">int</span> inode,iedge,cntout;</span><br></pre></td></tr></table></figure>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">struct</span> <span class="title class_">Node</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="type">int</span> num;        <span class="comment">//此节点的人数</span></span><br><span class="line">    <span class="type">int</span> dis[maxn];  <span class="comment">//此节点距离楼层中每个出口的距离</span></span><br><span class="line">    Node *nxt[maxn];<span class="comment">//指向跟这个节点与出口i距离相同的下一个节点</span></span><br><span class="line">    <span class="type">bool</span> narrow;   <span class="comment">//这个节点是否是窄道的入点、出点</span></span><br><span class="line">    Node *special;  <span class="comment">//窄道另一端的点 仅在isIN或isOUT为true时生效</span></span><br><span class="line">&#125;node[maxv];</span><br><span class="line"></span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">Edge</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="type">int</span> to,speed;   <span class="comment">//通道速度 单位时间内能通过通道的最大人数 宽道默认很大</span></span><br><span class="line">    <span class="type">bool</span> narrow;    <span class="comment">//是否为窄道</span></span><br><span class="line">&#125;edge[maxv&lt;&lt;<span class="number">3</span>];</span><br><span class="line"></span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">FLOOR</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="type">int</span> exitNum;        <span class="comment">//出口数目</span></span><br><span class="line">    <span class="type">int</span> nodeNum;        <span class="comment">//这层楼的节点总数</span></span><br><span class="line">    <span class="type">int</span> zero;           <span class="comment">//无人节点数</span></span><br><span class="line">    <span class="type">bool</span> isempty;       <span class="comment">//楼层是否为空</span></span><br><span class="line">    Node *Dnode[maxn][maxd] <span class="comment">//与第i个出口距离为j的节点组成的链表的头节点指针</span></span><br><span class="line">&#125;floor[maxf];</span><br></pre></td></tr></table></figure>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">void</span> <span class="title">init</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    inode = iedge = cntout = <span class="number">-1</span>;</span><br><span class="line">    <span class="built_in">memset</span>(head,<span class="number">-1</span>,<span class="built_in">sizeof</span>(head));</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​<br />
​</p>
<h4 id="题目描述"><a class="markdownIt-Anchor" href="#题目描述"></a> 题目描述</h4>
<p><strong>2019 ICM<br />
Problem D: Time to leave the Louvre</strong><br />
The increasing number of terror attacks in France[1]<br />
requires a review of the emergency<br />
evacuation plans at many popular destinations. Your ICM team is helping to<br />
design evacuation<br />
plans at the Louvre in Paris, France. In general, the goal of evacuation is to<br />
have all occupants<br />
leave the building as quickly and safely as possible. Upon notification of a<br />
required evacuation,<br />
individuals egress to and through an optimal exit in order to empty the<br />
building as quickly as<br />
possible.<br />
The Louvre is one of the world’s largest and most visited art museum,<br />
receiving more than 8.1<br />
million visitors in 2017[2]<br />
. The number of guests in the museum varies throughout the day and<br />
year, which provides challenges in planning for regular movement within the<br />
museum. The<br />
diversity of visitors – speaking a variety of languages, groups traveling<br />
together, and disabled<br />
visitors – makes evacuation in an emergency even more challenging.<br />
The Louvre has five floors, two of which are underground.<br />
![在这里插入图片描述](<a target="_blank" rel="noopener" href="https://img-blog.csdnimg.cn/20210112235110425.png?x-oss-">https://img-blog.csdnimg.cn/20210112235110425.png?x-oss-</a><br />
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70#pic_center)<br />
The 380,000 exhibits located on these five floors cover approximately 72,735<br />
square meters,<br />
with building wings as long as 480 meters or 5 city blocks[3]. The pyramid<br />
entrance is the main<br />
and most used public entrance to the museum. However, there are also three<br />
other entrances<br />
usually reserved for groups and individuals with museum memberships: the<br />
Passage Richelieu<br />
entrance, the Carrousel du Louvre entrance, and the Portes Des Lions entrance.<br />
The Louvre has<br />
an online application, “Affluences” (<a target="_blank" rel="noopener" href="https://www.affluences.com/louvre.php">https://www.affluences.com/louvre.php</a>),<br />
that provides realtime updates on the estimated waiting time at each of these<br />
entrances to help facilitate entry to<br />
the museum. Your team might consider how technology, to include apps such as<br />
Affluences, or<br />
others could be used to facilitate your evacuation plan.<br />
Only emergency personnel and museum officials know the actual number of total<br />
available exit<br />
points (service doors, employee entrances, VIP entrances, emergency exits, and<br />
old secret<br />
entrances built by the monarchy, etc.). While public awareness of these exit<br />
points could provide<br />
additional strength to an evacuation plan, their use would simultaneously<br />
cause security concerns<br />
due to the lower or limited security postures at these exits compared with<br />
level of security at the<br />
four main entrances. Thus, when creating your model, your team should consider<br />
carefully when<br />
and how any additional exits might be utilized.<br />
Your supervisor wants your ICM team to develop an emergency evacuation model<br />
that allows<br />
the museum leaders to explore a range of options to evacuate visitors from the<br />
museum, while<br />
also allowing emergency personnel to enter the building as quickly as<br />
possible. It is important to<br />
identify potential bottlenecks that may limit movement towards the exits. The<br />
museum<br />
emergency planners are especially interested in an adaptable model that can be<br />
designed to<br />
address a broad set of considerations and various types of potential threats.<br />
Each threat has the<br />
potential to alter or remove segments of possible routes to safety that may be<br />
essential in a single<br />
optimized route. Once developed, validate your model(s) and discuss how the<br />
Louvre would<br />
implement it.<br />
Based on the results of your work, propose policy and procedural<br />
recommendations for<br />
emergency management of the Louvre. Include any applicable crowd management<br />
and control<br />
procedures that your team believes are necessary for the safety of the<br />
visitors. Additionally,<br />
discuss how you could adapt and implement your model(s) for other large,<br />
crowded structures.<br />
Your submission should consist of:<br />
 One-page Summary Sheet,<br />
 Your solution of no more than 20 pages, for a maximum of 21 pages with your<br />
summary.<br />
 Judges expect a complete list of references with in-text citations, but may<br />
not consider<br />
appendices in the judging process.<br />
 Note: Reference list and any appendices do not count toward the 21-page<br />
limit and<br />
should appear after your completed solution.<br />
References:<br />
[1] Reporters, Telegraph. “Terror Attacks in France: From Toulouse to the<br />
Louvre.” The<br />
Telegraph, Telegraph Media Group, 24 June 2018,<br />
<a target="_blank" rel="noopener" href="http://www.telegraph.co.uk/news/0/terrorattacks-france-toulouse-louvre/">www.telegraph.co.uk/news/0/terrorattacks-france-toulouse-louvre/</a>. [2] “8.1<br />
Million Visitors to the Louvre in 2017.” Louvre Press Release, 25 Jan. 2018,<br />
<a target="_blank" rel="noopener" href="http://presse.louvre.fr/8-1-million-visitors-to-the-louvre-in-2017/">presse.louvre.fr/8-1-million-visitors-to-the-louvre-in-2017/</a>. [3] “Interactive<br />
Floor Plans.” Louvre - Interactive Floor Plans | Louvre Museum | Paris,<br />
30 June 2016, <a target="_blank" rel="noopener" href="http://www.louvre.fr/en/plan">www.louvre.fr/en/plan</a>.<br />
[4] “Pyramid” Project Launch – The Musée du Louvre is improving visitor<br />
reception<br />
(2014-2016).” Louvre Press Kit, 18 Sept. 2014,<br />
<a target="_blank" rel="noopener" href="http://www.louvre.fr/sites/default/files/dp_pyramide%2028102014_en.pdf">www.louvre.fr/sites/default/files/dp_pyramide 28102014_en.pdf</a>.<br />
[5] “The ‘Pyramid’ Project - Improving Visitor Reception (2014-2016).” Louvre<br />
Press<br />
Release, 6 July 2016, <a target="_blank" rel="noopener" href="http://presse.louvre.fr/the-pyramid-project/">presse.louvre.fr/the-pyramid-project/</a>.<br />
Glossary:<br />
Bottlenecks – places where movement is dramatically slowed or even stopped.<br />
Emergency personnel – people who help in an emergency, such as guards, fire<br />
fighters,<br />
medics, ambulance crews, doctors, and police.</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%EF%BC%88%E5%BC%BA%E8%A1%8C%E7%AE%97%E6%B3%95%EF%BC%89%E5%AF%B92019%E7%82%B9%E7%BE%8E%E8%B5%9BD%E9%A2%98%E6%9E%81%E7%AB%AF%E5%8C%96%E7%9A%84%E7%AE%97%E6%B3%95%E6%8E%A2%E8%AE%A8%E3%80%81%E8%AE%BE%E8%AE%A1%E4%B8%8E%E9%81%87%E5%88%B0%E7%9A%84%E9%97%AE%E9%A2%98%EF%BC%88%E6%9C%AA%E5%AE%8C,%E4%BD%86%E5%8F%AF%E8%83%BD%E4%B9%9F%E5%88%B0%E6%AD%A4%E4%B8%BA%E6%AD%A2%EF%BC%89/" data-id="cl2uhoefb00fze4j3bx2p2jz2" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E6%9D%82%E4%B9%B1/" rel="tag">杂乱</a></li></ul>

    </footer>
  </div>
  
</article>




  
    <article id="post-disabled/【屑】【学习记录】【Python】自己能看明白的关于学习bs4.BeautifulSoup基本知识的总结" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/disabled/%E3%80%90%E5%B1%91%E3%80%91%E3%80%90%E5%AD%A6%E4%B9%A0%E8%AE%B0%E5%BD%95%E3%80%91%E3%80%90Python%E3%80%91%E8%87%AA%E5%B7%B1%E8%83%BD%E7%9C%8B%E6%98%8E%E7%99%BD%E7%9A%84%E5%85%B3%E4%BA%8E%E5%AD%A6%E4%B9%A0bs4.BeautifulSoup%E5%9F%BA%E6%9C%AC%E7%9F%A5%E8%AF%86%E7%9A%84%E6%80%BB%E7%BB%93/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/1111/11/11/disabled/%E3%80%90%E5%B1%91%E3%80%91%E3%80%90%E5%AD%A6%E4%B9%A0%E8%AE%B0%E5%BD%95%E3%80%91%E3%80%90Python%E3%80%91%E8%87%AA%E5%B7%B1%E8%83%BD%E7%9C%8B%E6%98%8E%E7%99%BD%E7%9A%84%E5%85%B3%E4%BA%8E%E5%AD%A6%E4%B9%A0bs4.BeautifulSoup%E5%9F%BA%E6%9C%AC%E7%9F%A5%E8%AF%86%E7%9A%84%E6%80%BB%E7%BB%93/">【屑】【学习记录】【Python】自己能看明白的关于学习bs4.BeautifulSoup基本知识的总结.md</a>
    </h1>
  

        <div>
          
          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<p>留着日后看<br />
学习网址：<a target="_blank" rel="noopener" href="https://fishc.com.cn/thread-97807-1-1.html">https://fishc.com.cn/thread-97807-1-1.html</a><br />
![page1](<a target="_blank" rel="noopener" href="https://img-blog.csdnimg.cn/20200222175719367.jpg?x-oss-">https://img-blog.csdnimg.cn/20200222175719367.jpg?x-oss-</a><br />
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70)<br />
![page2](<a target="_blank" rel="noopener" href="https://img-blog.csdnimg.cn/20200222175804505.jpg?x-oss-">https://img-blog.csdnimg.cn/20200222175804505.jpg?x-oss-</a><br />
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70)<br />
![page3](<a target="_blank" rel="noopener" href="https://img-blog.csdnimg.cn/20200222175818432.jpg?x-oss-">https://img-blog.csdnimg.cn/20200222175818432.jpg?x-oss-</a><br />
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70)</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/disabled/%E3%80%90%E5%B1%91%E3%80%91%E3%80%90%E5%AD%A6%E4%B9%A0%E8%AE%B0%E5%BD%95%E3%80%91%E3%80%90Python%E3%80%91%E8%87%AA%E5%B7%B1%E8%83%BD%E7%9C%8B%E6%98%8E%E7%99%BD%E7%9A%84%E5%85%B3%E4%BA%8E%E5%AD%A6%E4%B9%A0bs4.BeautifulSoup%E5%9F%BA%E6%9C%AC%E7%9F%A5%E8%AF%86%E7%9A%84%E6%80%BB%E7%BB%93/" data-id="cl2uhoefb00g0e4j39hed37d5" class="article-share-link">分享</a>
      
      
    </footer>
  </div>
  
</article>




  


  <nav id="page-nav">
    <a class="extend prev" rel="prev" href="/page/7/">&lt;&lt;&lt; 上一页</a><a class="page-number" href="/">1</a><span class="space">&hellip;</span><a class="page-number" href="/page/6/">6</a><a class="page-number" href="/page/7/">7</a><span class="page-number current">8</span>
  </nav>
</section>
        
          <aside id="sidebar">
  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <h1 class="blog-title">蓝湖畔淅淅沥沥的雨</h1>
    <h2 class="blog-subtitle">All tragedy erased, I see only wonders...</h2>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>



    <div class="social-link">
      
        <a class="hvr-bounce-in" href="https://github.com/Wldcmzy" target="_blank" title="Github">
          Github
        </a>
      
        <a class="hvr-bounce-in" href="https://blog.csdn.net/wldcmzy" target="_blank" title="CSDN">
          CSDN
        </a>
      
        <a class="hvr-bounce-in" href="https://space.bilibili.com/83743701" target="_blank" title="bilibili(无技术和学习内容)">
          bilibili(无技术和学习内容)
        </a>
      
    </div>

    <div class="friend-link">
      <h2>友情链接</h2>
      
        <a class="hvr-bounce-in" href="https://shanamaid.github.io/" target="_blank" title="夏娜主题作者的博客">
          夏娜主题作者的博客
        </a>
      
    </div>
  </div>
</div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy;2021 - 2022 StarsWhisper<br>
      由<a href="http://hexo.io/" target="_blank">Hexo</a>强力驱动 | 
      主题-<a target="_blank" rel="noopener" href="https://github.com/ShanaMaid/hexo-theme-shana">Shana</a>(但是魔改)
      
    </div>
    
  </div>
</footer>
    </div>
    

<script src="//apps.bdimg.com/libs/jquery/2.1.4/jquery.min.js"></script>
<script src="//apps.bdimg.com/libs/wow/0.1.6/wow.min.js"></script>
<script>
new WOW().init();
</script>   


  
<link rel="stylesheet" href="/plugin/fancybox/jquery.fancybox.css">

  
<script src="/plugin/fancybox/jquery.fancybox.pack.js"></script>




  
<link rel="stylesheet" href="/plugin/galmenu/GalMenu.css">

  
<script src="/plugin/galmenu/GalMenu.js"></script>

  <div class="GalMenu GalDropDown">
      <div class="circle" id="gal">
        <div class="ring">
          
            <a href="/announcement" title="" class="menuItem">公告</a>
          
            <a href="/tags" title="" class="menuItem">标签</a>
          
            <a href="/categories" title="" class="menuItem">分类</a>
          
            <a href="/archives" title="" class="menuItem">归档</a>
          
            <a href="/knightabout" title="" class="menuItem">关于</a>
          
            <a href="/bridges" title="" class="menuItem">传送门</a>
          
        </div>
        
          <audio id="audio" src="#"></audio>
        
      </div> 
</div>
<div id="overlay" style="opacity: 1; cursor: pointer;"></div>
  <script type="text/javascript">var items = document.querySelectorAll('.menuItem');
    for (var i = 0,
    l = items.length; i < l; i++) {
      items[i].style.left = (50 - 35 * Math.cos( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%";
      items[i].style.top = (50 + 35 * Math.sin( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%"
    }</script>
<script type="text/javascript">
  $(document).ready(function() {
    $('body').GalMenu({
      'menu': 'GalDropDown'
    })
  });
</script>

  <section class="hidden-xs"> 
  <ul class="cb-slideshow"> 
    <li><span>苟利</span></li> 
    <li><span>国家</span></li> 
    <li><span>生死以</span></li> 
    <li><span>岂能</span></li> 
    <li><span>祸福</span></li> 
    <li><span>趋避之</span></li> 
  </ul>
</section>

<script src="/js/script.js"></script>




  </div>
</body>
</html>